#include "../LeetCodeShell/common.h"

double Pow(double x, int n)
{
	if(n==0){
		return 1.0;
	}

	double prod = 1.0;
	double base = n>0? x : 1.0/x;
	int rest = n>0? n : -n;
	while(rest>0){
		if(rest&1!=0){
			prod *= base;
		}
		rest >>= 1;
		base *= base;
	}
	return prod;
}
